/*
 * @lc app=leetcode.cn id=440 lang=typescript
 *
 * [440] 字典序的第K小数字
 */

// @lc code=start
function findKthNumber(n: number, k: number): number {
  // 当前数字所能表示的范围
  const getSteps = (num: number, n: number): number => {
    let steps = 0;
    let lastNum = num;
    let firstNum = num;
    while (firstNum <= n) {
      steps += Math.min(lastNum, n) - firstNum + 1;
      firstNum *= 10;
      lastNum = lastNum * 10 + 9;
    }
    return steps;
  };

  let ans = 1;
  k--;
  while (k > 0) {
    const steps = getSteps(ans, n);
    if (steps <= k) {
      k -= steps;
      ans++;
    } else {
      ans *= 10;
      k--;
    }
  }

  return ans;
}
// @lc code=end
